Electronic circuits, such as integrated microcircuits, are used in a variety of products, from automobiles to microwaves to personal computers. Designing and fabricating microcircuit devices typically involves many steps, known as a “design flow.” The particular steps of a design flow often are dependent upon the type of microcircuit being designed, its complexity, the design team, and the microcircuit fabricator or foundry that will manufacture the microcircuit. Typically, software and hardware “tools” will verify a design at various stages of the design flow by running software simulators and/or hardware emulators, and errors in the design are corrected.
Several steps are common to most design flows. Initially, the specification for the new microcircuit is transformed into a logical design, such as a register transfer level (RTL) description of the circuit. With this type of logical design, the circuit is described in terms of both the exchange of signals between hardware registers and the logical operations that are performed on those signals. The logical design typically employs a Hardware Design Language (HDL), such as the Very high speed integrated circuit Hardware Design Language (VHDL). The logical design of the circuit is then analyzed, to confirm that the operational logic incorporated into the design will accurately perform the functions desired for the circuit. This analysis is sometimes referred to as “functional verification.”
After the accuracy of the logical design is confirmed, it is converted into a device design by synthesis software. The device design, which is typically in the form of a schematic or netlist, describes the specific electronic devices (such as transistors, resistors, and capacitors) that will be used in the circuit, along with their interconnections. Preliminary timing estimates for portions of the circuit may be made at this stage, using an assumed characteristic speed for each device. In addition, the relationships between the electronic devices are analyzed, to confirm that the circuit described by the device design will correctly perform the functions desired for the circuit. This analysis is sometimes referred to as “formal verification.”
Once the relationships between circuit devices have been established, the design is again transformed, this time into a physical design that describes specific geometric elements. This type of design often is referred to as a “layout” design. The geometric elements define the shapes that will be created in various materials to actually manufacture the circuit device components (e.g., contacts, gates, etc.) making up the circuit. While the geometric elements are typically polygons, other shapes, such as circular and elliptical shapes, also may be employed. After the physical layout design has been finalized, it is then converted into a format that can be employed by a mask or reticle writing tool to create a mask or reticle for use in a photolithographic manufacturing process, or, alternately, into format that can be employed by an electron-beam writing tool in an electron beam manufacturing process.
The increasing cost of design and increased pressure on time-to-market schedules has given rise to design reuse, to the extent that a significant portion of an integrated circuit design may comprise reusable components. These reusable components are often referred to in the electronics field as “intellectual property” or “IP” components. IP components may be logical IP components incorporating logical design data, or they may be physical IP components incorporating physical layout design data. A microcircuit design company will typically license IP components from other parties, so most microcircuit design company will desire to track and manage their use to comply with the license agreements. On the other hand, companies that provide IP components seek to detect when their IP components are being infringed by uses outside of their license agreements.
This rapid proliferation of IP components has accelerated the dual problem of IP component tracking/management and IP component infringement detection. The exponential increase in the data set size of physical IP components in particular has increased the computational challenge of managing physical IP assets within an organization. With ever more emphasis on compliance requirements, the problem of tracking physical IP component layout data in, for example, Terabyte scale designs, with modest computational resources, in a timely and accessible manner, has come to the forefront.
To further complicate the tracking and management of physical IP components, a physical layout design typically will be hierarchically organized into discrete design portions or “cells.” In some situations, an IP component may represent only a single cell in a larger hierarchical design. In other situations, an IP component may represent multiple cells of differing hierarchy. The proliferation of cells in both design and analysis processes has accelerated the need for cell tracking and identification based on physical layout data.
Various techniques have been employed to recognize cells or IP components in a design that match a given cell or IP component template. One commonly used set of techniques identifies matching cells or IP components based upon name recognition. These techniques are easily circumvented, even unintentionally, simply by changing the names of the cells in a design. Renaming of cells is frequently done for a number of reasons, including a desire to use a consistent internal naming convention, avoiding disclosure of trade secret sourcing information, etc.
Another set of techniques that have been employed to recognize matching cells (and thus IP components) employ geometry recognition. These techniques recognize similar geometric shapes and shape arrangements in layout data. One common geometry recognition technique, referred to as XOR checking, uses a layout XOR operation on the designs being compared. If the result of the XOR operation is substantially a null set, then the two designs substantially match. This technique is computationally expensive, however, and is not amenable to archival storage of layout signatures in a database. Further, this technique is difficult to employ if one cell being compared has been rotated or inverted relative to the other cell being compared. A variation of this technique uses some property of a cell, such as a bounding box for the cell or its layout area, to classify cells that are similar prior to performing an exhaustive XOR operation. This technique also suffers from the archival storage problem referenced above. Moreover, it is possible that a single rogue layer of data (deliberately inserted to obfuscate the comparison by a malicious adversary, for example) can prevent an XOR operation from being performed on otherwise matching cells.
Other techniques provide information describing the geometric elements into a canonical hash function to generate a signature. If the resulting signatures for two different cells are the same, then the cells are determined to be a match. These schemes suffer from a fundamental problem, however, in that conventional layout data representation formats are not canonical, and not order-dependent. That is, a geometric element can be represented as a point list, or as a collection of rectangles. Either representation results in the same photolithographic mask, but each would produce a substantially different hash signature. Further, a single geometric element may, in effect, match two or more separate geometric elements arranged to abut or overlap, but the single geometric element would produce a significantly different hash signature from the plurality of separate abutting or overlapping geometric elements.
Still other techniques use Fourier space transform to convert geometric element shapes to Fourier descriptors, which are canonical, and thus can be compared. These techniques require that the geometric elements be non-overlapping, however, and that the geometric elements in the designs being compared are ordered in the same direction (for example, from left-to-right). As noted, above, however, layout data sets typically are vector representations, and thus can be represented in many ways that cannot be compared even using Fourier descriptors.